public class ThreeWay {
    public int threeWay1(int n){
        int mod=(int)1e9+7;
        int []dp=new int[n+1];
        if (n==1||n==2) {return n;}
        if (n==3) {return 4;}

        for (int i=4;i<=n;i++){
            dp[i]=((dp[i-1]+dp[i-2])%mod+dp[i-3])%mod;
        }
        return dp[n];
    }
}
